package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/bitwise-and-of-numbers-range/description/?envType=study-plan-v2&envId=top-interview-150">数字范围按位与(https://leetcode.cn/problems/bitwise-and-of-numbers-range/description/?envType=study-plan-v2&envId=top-interview-150)</a>
 * <p>给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：left = 5, right = 7
 *      输出：4
 *
 * 示例 2：
 *      输入：left = 0, right = 0
 *      输出：0
 *
 * 示例 3：
 *      输入：left = 1, right = 2147483647
 *      输出：0
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>0 <= left <= right <= 2^31 - 1</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/24 16:48
 */
public class LC0201BitwiseANDofNumbersRange_M {

    static class Solution {
        /**
         * 方法一：位移。
         * <p>将两个数字不断向右移动，直到数字相等，即数字被缩减为它们的公共前缀。然后，通过将公共前缀向左移动，将零添加到公共前缀的右边以获得最终结果。
         *     <ul>
         *         <li>我们通过右移，将两个数字压缩为它们的公共前缀。在迭代过程中，我们计算执行的右移操作数。</li>
         *         <li>将得到的公共前缀左移相同的操作数得到结果。</li>
         *     </ul>
         * </p>
         */
        public int rangeBitwiseAnd(int left, int right) {
            // 观察按位与运算的性质。对于一系列的位，例如 [1,1,0,1,1]，只要有一个零值的位，那么这一系列位的按位与运算结果都将为零。
            // 对所有数字执行按位与运算的结果是所有对应二进制字符串的公共前缀再用零补上后面的剩余位。
            // 所有这些二进制字符串的公共前缀也即指定范围的起始和结束数字 m 和 n 的公共前缀==>给定两个整数，找到它们对应的二进制字符串的公共前缀
            int shift = 0;
            while (left != right) {
                left >>= 1;
                right >>= 1;
                ++shift;
            }
            return right << shift;
        }

        /**
         * 方法二：Brian Kernighan 算法。
         * <p>「Brian Kernighan 算法」，它用于清除二进制串中最右边的 1。
         *     <ul>
         *         <li>Brian Kernighan 算法的关键在于我们每次对 number 和 number−1之间进行按位与运算后，number 中最右边的 1 会被抹去变成 0。</li>
         *     </ul>
         *     <pre>
         *         12 : 0000 1100
         *  12-1 = 11 : 0000 1000
         *  -------------------------
         *         8  : 0000 1000
         *   8-1 = 7  : 0000 0111
         *   ------------------------
         *         0  : 0000 0000
         *
         *     </pre>
         * </p>
         *
         */
        public int rangeBitwiseAnd2(int left, int right) {
            // 观察按位与运算的性质。对于一系列的位，例如 [1,1,0,1,1]，只要有一个零值的位，那么这一系列位的按位与运算结果都将为零。
            // 对所有数字执行按位与运算的结果是所有对应二进制字符串的公共前缀再用零补上后面的剩余位。
            // 所有这些二进制字符串的公共前缀也即指定范围的起始和结束数字 m 和 n 的公共前缀==>给定两个整数，找到它们对应的二进制字符串的公共前缀
            while (left < right) {
                // 抹去最右边的 1
                right = right & (right - 1);
            }
            return right;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.rangeBitwiseAnd(5, 7));
        System.out.println(solution.rangeBitwiseAnd(0, 0));
        System.out.println(solution.rangeBitwiseAnd(1, 2147483647));
    }
}
